/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date Aug 27, 2014
 */
package zhoujian.oj.leetcode;

import java.util.ArrayList;
import java.util.List;

import org.junit.Test;

/**
 * @version 1.0
 * @description Given numRows, generate the first numRows of Pascal's triangle.
 * 
 *              For example, given numRows = 5, Return
 * 
 *              [ 
 *              		[1], 
 *              	   [1,1], 
 *              	  [1,2,1], 
 *              	 [1,3,3,1], 
 *              	[1,4,6,4,1] 
 *              ]
 */
public class PascalTriangle {
	
	public List<List<Integer>> generate(int numRows) {
		List<List<Integer>> res = new ArrayList<List<Integer>>();
		if (numRows <= 0)
			return res;
		for (int i = 0; i < numRows; i++) {
			List<Integer> tmp = new ArrayList<Integer>();
			for (int j = 0; j <= i; j++) {
				tmp.add(getNum(i, j));
			}
			res.add(tmp);
		}
		
		return res;
    }
	
	private int getNum(int n, int m) {
		if (0 == n || m == 0)
			return 1;
		
		if (m > n / 2)
			return getNum(n, n - m);
		
		// 可能溢出
		long d1 = getDNum(n, m);
		long d2 = getDNum(m);
		
		return (int) (d1 / d2);
	}
	
	private long getDNum(int n, int m) {
		long res = 1;
		while (m-- > 0) {
			res *= n--;
		}
		return res;
	}
	
	private long getDNum(int m) {
		long res = 1;
		for (int i = 2; i <= m; i++)
			res *= i;
		return res;
	}
	
	@Test
	public void test() {
		List<List<Integer>> res = generate(10);
		for (List<Integer> list : res) {
			for (int i : list) {
				System.out.print(i + ",");
			}
			System.out.println();
		}
	}
}
